//
// Created by Admin on 2021/9/20.
//

#include "linkedlist.h"

pLinklist makeList(){
    printf("请输入链表长度，并为每一个节点填充数据：\n");
    pLinklist linklist = calloc(1,sizeof(Linklist));
    scanf("%d",&linklist->length);
    for(int i=0;i<linklist->length;i++){
        pNode node = calloc(1,sizeof(Node));
        scanf("%d",&node->data);
        if(i==0){
            linklist->head = node;
            linklist->tail = node;
        }else{
            linklist->tail->next = node;
            linklist->tail = node;
        }
    }
    printf("数据填充完毕\n");
    return linklist;
}

void destroyList(pLinklist linklist){
    pNode current = linklist->head;
    pNode next = current->next;
    while(next!=NULL){
        free(current);
        current = next;
        next = current -> next;
    }
    free(current);
    free(linklist);
}

int compare(pNode n1,pNode n2){
    return n1->data - n2->data;
}

void sortList(pLinklist linklist){
    pNode head = linklist->head;
    //使用索引排序，先取得所有节点的指针
    int nodes_len = linklist->length;
    ppNode nodesIndex = calloc(nodes_len,sizeof(pNode));
    for(int i=0;i<nodes_len;i++){
        nodesIndex[i] = head;
        head = head->next;
    }
    //对索引进行排序
    for(int i=0;i<nodes_len;i++){
        for(int j=i;j<nodes_len;j++){
            //将较大的对象放到后面
            if(compare(nodesIndex[i],nodesIndex[j]) > 0){
                pNode tmp = nodesIndex[i];
                nodesIndex[i] = nodesIndex[j];
                nodesIndex[j] = tmp;
            }
        }
    }
    //根据索引重建链表
    linklist->head = nodesIndex[0];
    for(int i=1;i<nodes_len;i++){
        nodesIndex[i-1]->next = nodesIndex[i];
    }
    linklist->tail = nodesIndex[linklist->length - 1];
    linklist->tail->next = NULL;
    free(nodesIndex);
}

void insertNode(pLinklist linklist,DATA data,int position){
    pNode aim = linklist->head;
    pNode prev = NULL;
    if(position==-1){
        aim = linklist->tail;
    }else{
        while(position-- && aim->next!=NULL){
            prev = aim;
            aim = aim->next;
        }
    }
    //position=-1时，直接挂在末尾
    if(aim->next==NULL){
        if(position == -1) {
            aim->next = calloc(1, sizeof(Node));
            aim->next->data = data;
            linklist->tail = aim->next;
        } else{
            printf("位置信息输入错误，操作无效\n");
            return;
        }
    }else{
        //其他情况下，将新数据放到position所指位置
        //先记录后续节点的地址
        pNode tmp = aim;
        //换上新节点
        aim = calloc(1,sizeof(Node));
        prev->next = aim;
        aim->data = data;
        //挂上后续节点
        aim->next = tmp;
    }
    //更新长度
    ++linklist->length;
}

void removeNode(pLinklist linklist,int position){
    pNode aim = linklist->head;
    pNode prev;
    if(position == -1){
        aim = linklist->tail;
        prev = linklist->head;
        while(prev->next!=aim) prev = prev->next;
    }else {
        while (position-- && aim->next != NULL) {
            prev = aim;
            aim = aim->next;
        }
    }

    prev ->next = aim->next;
    free(aim);
    --linklist -> length;
}

void showList(pLinklist linklist){
    if(linklist==NULL){
        printf("**链表未初始化或已销毁**\n");
        return;
    }
    pNode head = linklist->head;
    printf("showList");
    while(head!=NULL){
        printf(" -> %d",head->data);
        head = head->next;
    }
    printf("\n");
}